package oj_kickstart;

import java.util.Scanner;

public class BuildPalindromes {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            int yes = 0;
            int N = sc.nextInt();
            int Q = sc.nextInt();
            String source = sc.next();
            int[][] count = new int[26][N + 1];
            for (int i = 0; i < source.length(); i++) {
                for (char j = 'A'; j <= 'Z'; j++) {
                    count[j - 'A'][i + 1] = count[j - 'A'][i];
                }
                count[source.charAt(i) - 'A'][i + 1]++;
            }
            for (int q = 0; q < Q; q++) {
                int l = sc.nextInt();
                int r = sc.nextInt();
                boolean exist = false;
                for (char j = 'A'; j <= 'Z'; j++) {
                    if ((count[j - 'A'][r] - count[j - 'A'][l - 1]) % 2 == 1) {
                        if (!exist) {
                            exist = true;
                        } else {
                            yes--;
                            break;
                        }
                    }
                }
                yes++;
            }
            System.out.println(String.format("Case #%d: %d", t + 1, yes));
        }
    }
}
